package dst.heap;

import java.util.ArrayList;
import java.util.List;
import list.functions.ListFunctions;

/**
 *
 * Fully Tested: No
 * Fully Documented: No
 * Created: 26-Apr-2012
 * Last Updated: 26-Apr-2012
 *
 * @param <T> the data stored in the MaxHeap
 * @author Shimu Wu
 */
public class MaxHeap<T extends Comparable<T>> {

    private ArrayList<T> list;

    private int size;

    /**
     * Creates a MaxHeap backed by the given List, therefore any changes
     * to the given list is reflected in the MaxHeap, and any changes
     * to the MaxHeap is reflected in the list. Note it is not advisable 
     * to change the list other than using the MaxHeap's public methods.
     * 
     * @param list 
     */
    public MaxHeap(List<T> list) {
        this.list = new ArrayList<T>(list.size());
        ListFunctions.addAll(list, this.list);

        this.size = list.size();
        buildMaxHeap();
    }

    /**
     * Standard build max heap procedure that creates a max heap out of 
     * an unsorted list of elements. Runs in O(n).
     */
    private void buildMaxHeap() {
        // Indexing start at 0
        for (int i = size - 1; i >= 0; i--) {
            percolateDown(i);
        }
    }

    /**
     * Swaps two elements at index i and j.
     * 
     * @param i
     * @param j 
     */
    private void swap(int i, int j) {
        T temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }

    /**
     * Returns the index of the left child.
     * 
     * @param i
     * @return 
     */
    private int left(int i) {
        return 2 * i + 1; // Because indexing start at 0
    }

    /**
     * Returns the index of the right child
     * @param i
     * @return 
     */
    private int right(int i) {
        return 2 * i + 2; // Because indexing start at 0
    }

    /**
     * Returns the index of the parent
     * @param i
     * @return 
     */
    private int parent(int i) {
        return (i + 1) / 2 - 1; // Because indexing start at 0
    }

    /**
     * Also known as max heapify, this method assumes the left and right
     * subtree rooted at i are max-heaps. Recursively swap the element 
     * with the largest element amongst its left and right child until
     * the element is in its correct place.
     * 
     * @param i 
     */
    private void percolateDown(int i) {
        int left, right;
        left = left(i);
        right = right(i);

        // No need to check if left or right is null, all done 
        // in method lessThan

        int largest;
        if (lessThan(i, left)) {
            largest = left;
        } else {
            largest = i;
        }

        if (lessThan(largest, right)) {
            largest = right;
        }

        if (largest != i) {
            swap(i, largest);
            percolateDown(largest);
        }
    }

    private void percolateUp(int i) {
        int parent = parent(i);

        if (lessThan(parent, i)) {
            swap(parent, i);
            percolateUp(parent);
        }
    }

    /**
     * Returns true iff list[i] is strictly less than list[j]. Note
     * this method returns false if list[j] is null.
     * 
     * @param i
     * @param j
     * @return 
     */
    private boolean lessThan(int i, int j) {
        if (j < size - 1) {
            return (list.get(i).compareTo(list.get(j)) < 0);
        } else {
            return false;
        }
    }

    /**
     * Returns the largest element in the heap. Note this does NOT remove
     * the element from the heap. Use extractMax if one wishes to do so.
     * Returns null if the heap is empty.
     * 
     * @return 
     */
    public T peekMax() {
        if (isEmpty()) {
            return null;
        }
        return list.get(0);
    }

    /**
     * Returns and removes the largest element in the heap. Returns
     * null if the heap is empty.
     * 
     * @return 
     */
    public T extractMax() {
        if (isEmpty()) {
            return null;
        }

        T max = list.get(0);

        swap(0, size - 1); // Swap it with the last element
        list.remove(size - 1);
        size--;
        percolateDown(0);

        return max;
    }

    public void insert(T element) {
        if (size == list.size()) {
            list.add(element);
        } else {
            list.set(size, element);
        }
        
        size++;
        percolateUp(size - 1);
    }

    /**
     * Returns true if this max heap is empty (i.e. contains no elements).
     * 
     * @return 
     */
    public boolean isEmpty() {
        return (size == 0);
    }
}

    /**
     * Given the index i of the current node, returns a pointer to the left
     * child. Returns null if the current does not hava a left child.
     * 
     * @param i the index of the current node
     * @return 
    
    private T left(int i) {
        int index = i * 2;
        if (index >= list.size()) {
            return null;
        } else {
            return list.get(index);
        }        
    }
    
    /**
     * Given the index i of the current node, returns a pointer to the
     * right child. Returns null if the current does not have a right child.
     * 
     * @param i the index of the current node
     * @return 

    private T right(int i) {
        int index = i * 2 + 1;
        if (index >= list.size()) {
            return null;
        } else {
            return list.get(i*2 + 1);
        }        
    } */